package codeRandomThoughts.Test222完全二叉树中的节点个数;

import codeRandomThoughts.utils.TreeNode;

/**
 * 递归写法,体会其中精髓
 */
public class Solution2 {
    public int countNodes(TreeNode root){
        if (root==null){
            return 0;
        }
        //看最左边和最右边的叶子节点深度是否相等,判断是否为完全二叉树
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth=0;
        int rightDepth=0;
        while (left!=null) {
            left=left.left;
            leftDepth++;
        }
        while (right!=null){
            right= right.right;
            rightDepth++;
        }
        if (leftDepth==rightDepth){
            return (2<<leftDepth)-1;
        }
        return countNodes(root.left)+countNodes(root.right)+1;
    }
}
